In a packet switched network, routing protocols determine the path that packets traverse through the network. Those routing protocols react to changes in the network (e.g., links going up and down, or link costs changing) and adjust the routes taken by packets through the network.
The routing protocols are often distributed, in that they are implemented in a coordinated fashion by many routers in the network, and they are dynamic, in that they react to changes in the network. As such, the routes taken by packets will change over time, often in unanticipated ways.
In such a network, it is important to understand the nature of routing changes, as these changes impact the stability of the network and the level of service (i.e., loss and delay) experienced by packets.
Network operators and service providers have invested a great deal in understanding the dynamics and stability of routing within their networks. Previous approaches include:
1. Monitoring of routing protocol message exchanges by specialized route monitors. These messages can then be used to infer the state of routing in the network.
2. Monitoring of router log messages that identify when events (e.g., link failures) have occurred.
3. Active end-to-end measurement of the data plane to infer the stability and performance of the network.
The first two approaches measure the control plane directly but are unable to give precise information about the control plane on short timescales and on all routers. That is, those approaches can identify that changes have occurred, but they can neither precisely assess the impact of those changes nor can they necessarily determine when the impact was experienced at each individual router.
The third approach measures the impact of routing changes on the data plane, but again, only in a coarse and imprecise manner.
There is therefore a need for an improved method for detecting and measuring routing changes in a packet-switched network.